package com.briup.ch04;

import java.util.Arrays;

public class Test5 {
    public static void bubbleSort(int[] arr)
    {
        //升序排血
        //10 9 8 7 6 5 4 3 2 1
        //第一轮
        //9 10 8 7 6 5 4 3 2 1
        //9 8 10 7 6 5 4 3 2 1
        //9 8 7 10 6 5 4 3 2 1
        //9 8 7 6 10 5 4 3 2 1
        //9 8 7 6 5 10 4 3 2 1
        //9 8 7 6 5 4 10 3 2 1
        //9 8 7 6 5 4 3 10 2 1
        //9 8 7 6 5 4 3 2 10 1
        //9 8 7 6 5 4 3 2 1 10
        //第二轮
        //8 9 7 6 5 4 3 2 1 10
        //8 7 9 6 5 4 3 2 1 10
        //8 7 6 9 5 4 3 2 1 10
        //8 7 6 5 9 4 3 2 1 10
        //8 7 6 5 4 9 3 2 1 10
        //8 7 6 5 4 3 9 2 1 10
        //8 7 6 5 4 3 2 9 1 10
        //8 7 6 5 4 3 2 1 9 10
        //...
        //第9论
        //1 2 3 4 5 6 7 8 9 10
        //总结一共比较了n-1论，每轮比较n-1-i次
        //控制轮数
        for (int i = 0; i < arr.length-1; i++) {
            //控制比较次数
            for(int j=0;j<arr.length-1-i;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    arr[j]=arr[j]^arr[j+1];
                    arr[j+1]=arr[j]^arr[j+1];
                    arr[j]=arr[j]^arr[j+1];
                }
            }
        }

    }
    public static void selectSort(int[] arr)
    {
        //10 9 8 7 6 5 4 3 2 1
        //每次寻找最小值下标
        //第一次
        //最小值下表是9，和第一个元素交换
        //1 9 8 7 6 5 4 3 2 10
        //第二次
        //从第二个语速开始找最小值下表
        //最小值下表是8，和第二个元素交换
        //1 2 8 7 6 5 4 3 9 10
        //...
        //第9次
        //1 2 3 4 5 6 7 8 9 10
        int min=0;
        for (int i = 0; i < arr.length-1; i++) {
            min=i;
            for (int j = i; j < arr.length; j++) {

                if(arr[j]<arr[min])
                {
                    min=j;
                }
            }
            arr[i]=arr[i]^arr[min];
            arr[min]=arr[i]^arr[min];
            arr[i]=arr[i]^arr[min];
        }
    }


    public static void insertSort(int[] arr)
    {
        //10 9 8 7 6 5 4 3 2 1
        //假设前n个元素有序，然后将新的而元素插入这个有序的元素
        //前1个元素有序 10
        //插入第二个元素，然后第二个元素和第一个元素比较 9
        //交换 9 10
        //前2个元素有序 9 10
        //插入第三个元素，和前2个元素比较 8
        //交换 8 9 10
        //前3个元素有序 8 9 10
        //插入第4个元素，和前3个比较 7
        //交换7 8 9 10
        //。。。
        //前9个元素有序
        //插入第10个元素，第10个和前9个比较 1
        //交换1 2 3 4 5 6 7 8 9 10
        
        //从1开始默认前一个元素是有序的，后续增加也就意味着前i个元素有序
        for (int i = 1; i < arr.length; i++) {
            //i=2 9 10 insert 8
            if(arr[i]<arr[i-1])//8<10
            {
                int tmp = arr[i];//temp=8
                int j;
                for (j = i - 1; j >= 0 && arr[j] >tmp; j--)
                {
                    arr[j+1] = arr[j];
                }
                arr[j+1] = tmp;
            }
        }
    }
    public static void shellSort(int[] arr)
    {
        /*步骤：
        1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再gap--，重复上述操作。
        2.当gap==1时就是直接插入排序，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。*/
        int n=arr.length;
        while(n>1)
        {
            n=n/3+1;
            for (int i = n; i < arr.length; i++) {
                int temp=arr[i];
                int j;
                for (j = i-n; j>=0&&arr[j]>temp; j-=n) {
                    arr[j+n]=arr[j];
                }
                arr[j+n]=temp;

            }
        }
    }
    public static void main(String[] args) {
        int[] arr1={10,9,8,7,6,5,4,3,2,1};
        bubbleSort(arr1);
        System.out.println(Arrays.toString(arr1));
        int[] arr2={10,9,8,7,6,5,4,3,2,1};
        selectSort(arr2);
        System.out.println(Arrays.toString(arr2));
        int[] arr3={10,9,8,7,6,5,4,3,2,1};
        insertSort(arr3);
        System.out.println(Arrays.toString(arr3));
        int[] arr4={10,9,8,7,6,5,4,3,2,1};
        shellSort(arr4);
        System.out.println(Arrays.toString(arr4));
    }
}
